package top.ivansong92.example.leetcode.learning.common.algorithms.dynamic;


import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestExample3 {

    public void test() {
        int i = 8;
        while ((i -= 3) > 0);
        System.out.println("i = " + i);
    }

    public static void main(String[] args) {
        TestExample3 hello = new TestExample3();
        for (int i = 0; i < 50_000; i++) {
            hello.test();
        }
    }


    @Test
    public void testintegerBreak() {
        System.out.println(lengthOfLISV2(new int[]{10,9,2,5,3,7,101,18}));
    }

    /**
     * 300. 最长递增子序列
     * @param nums
     * @return
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        if (len == 2) {
            return nums[1] > nums[0] ? 2 : 1;
        }

        Integer[] ltsResArray = new Integer[len];
        int res = 1;
        for(int i = 0; i < len; i ++) {
            res = Math.max(res, 1 + doGetMaxLength(nums, i + 1, len, nums[i], ltsResArray));
        }
        return res;
    }

    private int doGetMaxLength(int[] nums, int index, int max, int parentVal, Integer[] array) {
        if (index >= max) {
            return 0;
        }

        Integer val = array[index];
        if (val != null) {
            return val;
        }

        int res = 0;
        for (int i = index; i < max; i++) {
            if (nums[i] > parentVal) {
                res = Math.max(res, 1 + doGetMaxLength(nums, i + 1, max, nums[i], array));
            }
        }
        array[index] = res;
        return res;
    }


    public int lengthOfLISV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        if (len == 2) {
            return nums[1] > nums[0] ? 2 : 1;
        }

        int[] ltsResArray = new int[len];
        Arrays.fill(ltsResArray, 1);
        int res = 1;
        for (int i = 1; i < len; i++) {
            int val = nums[i];
            int newLtsVal = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < val) {
                    newLtsVal = Math.max(newLtsVal, ltsResArray[j] + 1);
                }
            }
            res = Math.max(newLtsVal, res);
            ltsResArray[i] = newLtsVal;
        }
        //查询list
        List<Integer> list = new ArrayList<>(res);
        int from = res;
        for (int i = len - 1; i >= 0; i--) {
            if (ltsResArray[i] == from) {
                list.add(nums[i]);
                from--;
            }
        }

        return res;
    }


    /**
     * 376. 摆动序列
     * @param nums
     * @return
     */

    public int wiggleMaxLength(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        if (len == 2) {
            return nums[1] == nums[0] ? 1 : 2;
        }
        int[][] maxResArray = new int[len][2];
        maxResArray[0] = new int[]{1, 1};
        int res = 0;
        for (int i = 1; i < len; i++) {
            int left = 1, right = 1, val = nums[i];
            for (int j = 0; j < i; j ++) {
                if (val > nums[j]) {
                    left = Math.max(left, 1 + maxResArray[j][1]);
                } else if (val < nums[j]) {
                    right = Math.max(right, 1 + maxResArray[j][0]);
                }
            }
            maxResArray[i] = new int[]{left, right};
            res = Math.max(res, Math.max(left, right));
        }
        return res;
    }
    //递归：记忆化搜索
    public int wiggleMaxLengthV2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int len = nums.length;
        if (len == 1) {
            return 1;
        }

        if (len == 2) {
            return nums[1] == nums[0] ? 1 : 2;
        }

        Integer[][] wiggleMaxArray = new Integer[len][2];
        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, 1 + doGetWiggleMax(nums, i + 1, len, 0, wiggleMaxArray, nums[i]));
            res = Math.max(res, 1 + doGetWiggleMax(nums, i + 1, len, 1, wiggleMaxArray, nums[i]));
        }
        return res;
    }

    private int doGetWiggleMax(int[] nums, int index, int n, int dir, Integer[][] array, int parentVal) {
        if (index >= n) {
            return 0;
        }

        Integer val = array[index][dir];
        if (val != null) {
            return val;
        }

        boolean left = dir == 0;
        int res = 0;
        for (int i = index; i < n; i++) {
            if (left) {
                if (nums[i] < parentVal) {
                    res = Math.max(res, 1 + doGetWiggleMax(nums, i + 1, n, 1, array, nums[i]));
                }
            } else {
                if (nums[i] > parentVal) {
                    res = Math.max(res, 1 + doGetWiggleMax(nums, i + 1, n, 0, array, nums[i]));
                }
            }
        }
        array[index][dir] = res;
        return  res;
    }
}